package com.gitee.ywj1352.算法.week06;

import java.util.*;

public class 合并区间问题 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        List<int[]> res = new ArrayList<int[]>();

        // Api
        for (int i = 0; i < intervals.length; ) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            while (i < intervals.length - 1 && r >= intervals[i + 1][0]) {
                r = Math.max(r, intervals[i + 1][1]);
                i++;
            }
            res.add(new int[]{l, r});
            i++;
        }
        return res.toArray(new int[0][0]);
    }


    public static void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int i0 = 0, i2 = nums.length - 1, i = 0;
        while (i <= i2) {
            if (nums[i] == 2) {
                swap(nums, i, i2);
                i2--;
            } else if (nums[i] == 0) {
                if (i == i0) {
                    i++;
                    i0++;
                } else {
                    swap(nums, i, i0);
                    i0++;
                }
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        char[][] arr = new char[][]{{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        int i = numIslands(arr);

        System.out.println(i);
    }


    public static int numIslands(char[][] grid) {
        int nums = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    ganren(grid, i, j);
                    nums++;
                }
            }
        }
        return nums;
    }


    static void ganren(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        if (grid[i][j] == '0') return;
        grid[i][j] = 0;
        ganren(grid, i + 1, j);
        ganren(grid, i - 1, j);
        ganren(grid, i, j + 1);
        ganren(grid, i, j - 1);
    }


    public List<Integer> findAnagrams(String s, String p) {
        char[] arr = p.toCharArray();
        Map<Character,Integer> map  = new HashMap<Character,Integer>(), window = new HashMap<Character,Integer>();
        for(char c : arr) map.put(c, map.getOrDefault(c, 0) + 1);
        int v = 0, left = 0 ;
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0 ; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.getOrDefault(c , 0)!= 0){
                window.put(c,map.getOrDefault(c , 0)+1);
                if(window.get(c) == map.get(c)) v ++;
            }
            while(i - left >= map.size()){
                if(v == map.size()) res.add(left);
                left ++;
                char lc = s.charAt(left);

                if(map.getOrDefault(lc,0)!=0){
                    if(window.get(c) == map.get(c)) v--;
                    window.put(c,window.get(c)-1);
                }
            }
        }

        return res;

    }
}
